GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Suchbaum</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Suchbaum</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p>In der <a href="Informatik" title="Informatik">Informatik</a> ist ein <b>Suchbaum</b> eine <a href="Abstrakter_Datentyp" title="Abstrakter Datentyp">abstrakte</a> <a href="Datenstruktur" title="Datenstruktur">Datenstruktur</a>, bei der die <a href="Menge_(Mathematik)" title="Menge (Mathematik)">Menge</a> von Elementen, in der gesucht werden soll, in einer <a href="Baum_(Graphentheorie)" title="Baum (Graphentheorie)">Baumstruktur</a> dargestellt wird.

Wie ein <a href="Assoziatives_Datenfeld" class="mw-redirect" title="Assoziatives Datenfeld">assoziatives Datenfeld</a> oder eine <a href="Hashtabelle" title="Hashtabelle">Hashtabelle</a> realisiert er eine endliche <a href="Funktion_(Mathematik)" title="Funktion (Mathematik)">Funktion</a> (<a href="Englische_Sprache" title="Englische Sprache">englisch</a>: <i>map</i>), bei der aus einem <a href="Schl%C3%BCssel_(Datenbank)" title="Schlüssel (Datenbank)">Suchschlüssel</a> (aus der endlichen <a href="Definitionsmenge" title="Definitionsmenge">Definitionsmenge</a>) ein Datenwert (aus der <a href="Bild_(Mathematik)" title="Bild (Mathematik)">Wertemenge</a>) gewonnen wird. Bei fehlender Wertemenge realisiert der Baum eine <a href="Indikatorfunktion" title="Indikatorfunktion">Indikatorfunktion</a>, entspricht also einer endlichen Menge (<a href="Englische_Sprache" title="Englische Sprache">englisch</a>: <i>set</i>).

</p><p>Aus Effizienzgründen besitzt die Menge allermeist eine <a href="Quasiordnung#Totale_Quasiordnung" title="Quasiordnung">totale Quasiordnung</a>, die auch eine <a href="Totalordnung" class="mw-redirect" title="Totalordnung">Totalordnung</a> sein kann. Dieser Ordnung entspricht im Baum eine Links-Rechts-Orientierung auf folgende Weise: »links« von einem Knoten gibt es keine größeren Elemente und »rechts« keine kleineren. Dadurch wird in Form des <a href="Bin%C3%A4re_Suche" title="Binäre Suche">„binären Suchens“</a> ein Prinzip namens <a href="Teile-und-herrsche-Verfahren" title="Teile-und-herrsche-Verfahren">„Teile und herrsche“</a> möglich, welches Suchzeiten erlaubt, die <a href="Logarithmus" title="Logarithmus">logarithmisch</a> in der Anzahl der Suchschlüssel sind.

</p><p>Es gibt Suchbäume sowohl in statischer (unveränderlicher) wie in dynamischer (durch Einfügen und Löschen von Elementen veränderbarer) Ausprägung, für welche sich die <a href="Baumstruktur" class="mw-redirect" title="Baumstruktur">Baumstruktur</a> besonders gut eignet.

</p>

<div class="mw-heading mw-heading2"><h2 id="Operationen">Operationen</h2></div>

<p>Die charakteristische <a href="Operation_(Informatik)" title="Operation (Informatik)">Operation</a> ist das <a href="Bin%C3%A4rer_Suchbaum#Suchen" title="Binärer Suchbaum"><i>Suchen</i></a>. Die meisten anderen Operationen, wie <a href="Bin%C3%A4rbaum#Einfügen,_Einfügepunkt" title="Binärbaum"><i>Einfügen</i></a>, <a href="Bin%C3%A4rbaum#Löschen" title="Binärbaum"><i>Löschen</i></a>, <a href="Bin%C3%A4rbaum#Iterative_Implementierung" title="Binärbaum"><i>Traversieren</i></a> werden von der unterliegenden <a href="Baumstruktur" class="mw-redirect" title="Baumstruktur">Baumstruktur</a> geerbt.

</p><p>Die Suchoperation gibt ein Element mit übereinstimmendem Schlüssel zurück oder, falls der Schlüssel nicht vorkommt, das NULL-Element oder ein im Sinne der <a href="Totalordnung" class="mw-redirect" title="Totalordnung">Totalordnung</a> nächstgelegenes anderes Element.

</p><p>Der maximale Aufwand für das Suchen, d. h. die Maximalzahl der erforderlichen Vergleiche, ist bei vorliegender <a href="Totalordnung" class="mw-redirect" title="Totalordnung">Totalordnung</a> <a href="Proportionalit%C3%A4t" title="Proportionalität">proportional</a> zur <a href="H%C3%B6he_(Graphentheorie)" title="Höhe (Graphentheorie)">Baumhöhe</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy"></span>. Ein Baum wird <a href="Balancierter_Baum" title="Balancierter Baum">balanciert</a> genannt, wenn dafür Sorge getragen ist, dass <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle h}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle h}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b26be3e694314bc90c3215047e4a2010c6ee184a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.339ex; height:2.176ex;" alt="{\displaystyle h}" loading="lazy"></span> stets logarithmisch in der Anzahl <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> der Elemente ist. Ohne solche Vorkehrung kann der Suchbaum <a href="Balancierter_Baum#Problem:_Entartung" title="Balancierter Baum">entarten</a> bis zum ungünstigen Fall, dass der Suchaufwand proportional wird zu <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Spezielle_Suchbäume"><span id="Spezielle_Suchb.C3.A4ume"></span>Spezielle Suchbäume</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Binärer_Suchbaum"><span id="Bin.C3.A4rer_Suchbaum"></span>Binärer Suchbaum</h3></div>

<div class="hauptartikel" role="navigation"><span class="hauptartikel-pfeil" title="siehe" aria-hidden="true" role="presentation">→ </span><i><span class="hauptartikel-text">Hauptartikel</span>: <a href="Bin%C3%A4rer_Suchbaum" title="Binärer Suchbaum">Binärer Suchbaum</a></i></div>

<p>Ein <a href="Bin%C3%A4rer_Suchbaum" title="Binärer Suchbaum">binärer Suchbaum</a> ist eine knotenbasierte <a href="Datenstruktur" title="Datenstruktur">Datenstruktur</a>, in der jeder <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> einen Schlüssel und maximal zwei <a href="Teilbaum" class="mw-redirect" title="Teilbaum">Teilbäume</a> enthält, den linken und den rechten. Alle Schlüssel des linken Teilbaums sind kleiner als der Schlüssel des Knotens und die des rechten Teilbaums größer. Jeder Teilbaum ist ein binärer Suchbaum. Es sind viele Varianten entwickelt worden, die der Degeneration entgegenwirken sollen.

</p><p>Die <a href="Zeitkomplexit%C3%A4t" title="Zeitkomplexität">Zeitkomplexität</a> für die Suche in einem <a href="Bin%C3%A4rer_Suchbaum" title="Binärer Suchbaum">binären Suchbaum</a> ist im <a href="Worst_Case" title="Worst Case">Worst Case</a> die Höhe des <a href="Baum_(Graphentheorie)" title="Baum (Graphentheorie)">Baums</a>, die für einen Baum mit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> Elementen so klein wie <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(\log \ n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(\log \ n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8f6b29d64c5c7af9fcfd1c041ee711c8a5ac707e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.993ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(\log \ n)}" loading="lazy"></span> sein kann.

</p><p>Keine <a href="Bin%C3%A4rbaum" title="Binärbaum">Binärbäume</a> sind folgende Suchbäume:

</p>

<ul><li><a href="Fibonacci-Heap" title="Fibonacci-Heap">Fibonacci-Heap</a></li>

<div class="hauptartikel" role="navigation"><span class="hauptartikel-pfeil" title="siehe" aria-hidden="true" role="presentation">→ </span><i><span class="hauptartikel-text">Hauptartikel</span>: <a href="B-Baum" title="B-Baum">B-Baum</a></i></div><p><a href="B-Baum" title="B-Baum">B-Bäume</a> sind Verallgemeinerungen von <a href="Bin%C3%A4rer_Suchbaum" title="Binärer Suchbaum">binären Suchbäumen</a>, da sie an jedem <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> eine variable Anzahl von <a href="Teilbaum" class="mw-redirect" title="Teilbaum">Teilbäumen</a> haben können. Während untergeordnete Knoten einen vordefinierten Bereich haben, werden sie nicht unbedingt mit Daten gefüllt, was bedeutet, dass B-Bäume möglicherweise etwas Platz verschwenden können. Der Vorteil ist, dass B-Bäume nicht so häufig rebalanciert werden müssen wie andere selbst-balancierende Bäume.

</p><p>Aufgrund des variablen Bereichs ihrer Knotenlänge sind <a href="B-Baum" title="B-Baum">B-Bäume</a> für Systeme optimiert, die große Datenblöcke lesen. Sie werden auch häufig in <a href="Datenbank" title="Datenbank">Datenbanken</a> verwendet.

</p><p>Die <a href="Zeitkomplexit%C3%A4t" title="Zeitkomplexität">Zeitkomplexität</a> für die Suche in einem <a href="B-Baum" title="B-Baum">B-Baum</a> beträgt <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(\log \ n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(\log \ n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8f6b29d64c5c7af9fcfd1c041ee711c8a5ac707e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.993ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(\log \ n)}" loading="lazy"></span>.

</p>

<div class="hauptartikel" role="navigation"><span class="hauptartikel-pfeil" title="siehe" aria-hidden="true" role="presentation">→ </span><i><span class="hauptartikel-text">Hauptartikel</span>: <a href="(a%2C_b)-Baum" title="(a, b)-Baum">(a, b)-Baum</a></i></div><p>Ein <a href="(a%2C_b)-Baum" title="(a, b)-Baum">(a, b)-Baum</a> ist ein Suchbaum, in dem alle <a href="Bl%C3%A4tter_und_innere_Knoten_in_der_Graphentheorie" title="Blätter und innere Knoten in der Graphentheorie">Blätter</a> die gleiche Tiefe haben. Jeder <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> hat mindestens einen und höchstens <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"></span> <a href="Nachfolger_(Graphentheorie)" class="mw-redirect" title="Nachfolger (Graphentheorie)">Nachfolger</a>, während die Wurzel mindestens 2 und höchstens <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"></span> Nachfolger hat.

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy"></span> können mit folgender Formel bestimmt werden:<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2\leq a\leq {\frac {(b+1)}{2}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/48c13c821a07827e3972d2b9c4cdc9ed26993b23.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:16.235ex; height:5.676ex;" alt="{\displaystyle 2\leq a\leq {\frac {(b+1)}{2}}}" loading="lazy"></span></dd></dl>

<p>Die <a href="Zeitkomplexit%C3%A4t" title="Zeitkomplexität">Zeitkomplexität</a> für die Suche nach einem <a href="(a%2C_b)-Baum" title="(a, b)-Baum">(a, b)-Baum</a> beträgt <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(\log \ n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(\log \ n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8f6b29d64c5c7af9fcfd1c041ee711c8a5ac707e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.993ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(\log \ n)}" loading="lazy"></span>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Ternärer_Suchbaum"><span id="Tern.C3.A4rer_Suchbaum"></span>Ternärer Suchbaum</h3></div>

<p>Ein ternärer Suchbaum ist eine <a href="Datenstruktur" title="Datenstruktur">Datenstruktur</a> in Gestalt eines <a href="Pr%C3%A4fixbaum" class="mw-redirect" title="Präfixbaum">Präfixbaums</a>, in der die Folge<a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">knoten</a><sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> entsprechend der <a href="Ordnungsrelation" title="Ordnungsrelation">Ordnungsrelation</a> geordnet sind.

</p><p>Jeder Knoten in einem ternären Suchbaum enthält 3 <a href="Zeiger_(Informatik)" title="Zeiger (Informatik)">Zeiger</a>:

</p>

<ol><li>Der mittlere Zeiger zeigt auf den Knoten, mit dessen <i>Wert</i>, dem aktuellen, sich die Zeichenkette fortsetzt.</li>

<li>Der linke Zeiger zeigt auf einen Knoten, dessen <i>Wert</i> kleiner ist als der aktuelle <i>Wert</i>.</li>

<li>Der rechte Zeiger zeigt auf einen Knoten, dessen <i>Wert</i> größer ist als der aktuelle <i>Wert</i>.</li></ol>

<p>Zusätzlich zu den drei Zeigern hat jeder Knoten ein Feld zum Markieren des Endes einer <a href="Zeichenkette" title="Zeichenkette">Zeichenkette</a> und ggf. ein Feld für weitere Benutzerdaten.

</p><p>Die untenstehende Grafik zeigt einen ternären Suchbaum, der die Zeichenketten „cute“, „cup“, „at“, „as“, „he“, „us“ und „v“ enthält. Dabei ist das Ende einer Zeichenkette durch Unterstreichung des letzten Zeichens markiert:

</p>

<pre> c

/ | \

a u h

| | | \

<ins>t</ins> t <ins>e</ins> u

/ / | | \

</pre>

<p>Beim Suchen in einem ternären Suchbaum wird der Suchschlüssel als eine Zeichenkette übergeben, für die getestet wird, ob ein <a href="Weg_(Graphentheorie)" title="Weg (Graphentheorie)">Pfad</a> sie enthält.

</p><p>Die <a href="Zeitkomplexit%C3%A4t" title="Zeitkomplexität">Zeitkomplexität</a> für die Suche in einem ausgeglichenen ternären Suchbaum beträgt <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(\log \ n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(\log \ n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8f6b29d64c5c7af9fcfd1c041ee711c8a5ac707e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.993ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(\log \ n)}" loading="lazy"></span>.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Weitere_auf_Bäumen_basierende_Suchstrukturen"><span id="Weitere_auf_B.C3.A4umen_basierende_Suchstrukturen"></span>Weitere auf Bäumen basierende Suchstrukturen</h2></div>

<p>Obwohl <a href="Komplexit%C3%A4tstheorie" title="Komplexitätstheorie">komplexitätstheoretische</a> Angaben <a href="Asymptotik" class="mw-redirect" title="Asymptotik">asymptotisch</a> zu verstehen sind, lassen sie sich am ehesten in die Praxis übertragen, wenn die gesamte Datenstruktur in einem gleichförmigen Medium, z. B. dem <a href="Arbeitsspeicher" title="Arbeitsspeicher">Arbeitsspeicher</a> (Hauptspeicher), untergebracht werden soll.

</p><p>Spielen dagegen Zugriffe zu externen <a href="Datenspeicher" title="Datenspeicher">Medien</a> eine Rolle, kommen weitergehende Überlegungen ins Spiel. Im Kontext der Suchbäume sei verwiesen auf die Artikel:

</p>

<li><a href="Indexstruktur" title="Indexstruktur">Indexstruktur</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Speicherkomplexität"><span id="Speicherkomplexit.C3.A4t"></span>Speicherkomplexität</h2></div>

<p>Der Speicherverbrauch eines Suchbaums ist – zusätzlich zu den Nutzdaten – im Allgemeinen linear in der Anzahl <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> der Elemente, also in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3c7bbe0124ae81792773344bc8709fc2f9c9910d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.054ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(n)}" loading="lazy"></span>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Laufzeitkomplexität"><span id="Laufzeitkomplexit.C3.A4t"></span>Laufzeitkomplexität</h2></div>

<p>Bei der <a href="Laufzeit_(Informatik)" title="Laufzeit (Informatik)">Laufzeit</a> unterscheidet man <a href="Operation_(Informatik)" title="Operation (Informatik)">Operationen</a> zum Suchen, Einfügen und Löschen. Bei den letzteren beiden ist in der Tabelle die Laufzeit für das Positionieren <i>nicht</i> mit eingerechnet, da dies nicht nur über das Suchen, sondern z. B. auch über das <a href="Traversierung" title="Traversierung">Traversieren</a> geschehen kann. Abhängig von der Art des Suchbaums werden <a href="Landau-Symbole" title="Landau-Symbole">asymptotische</a> <a href="Amortisierte_Laufzeitanalyse" title="Amortisierte Laufzeitanalyse">mittlere</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle <}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle <}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/33737c89a17785dacc8638b4d66db3d5c8670de1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.808ex; height:1.843ex;" alt="{\displaystyle <}" loading="lazy"></span> maximale (<a href="Worst_Case#Informatik" title="Worst Case">worst case</a>) Laufzeiten gegenübergestellt, wobei die maximale weggelassen ist, wenn sie mit der mittleren übereinstimmt.

</p>

<caption style="padding-bottom:1em">Laufzeitkomplexitäten

</caption>

<th style="width:17.2%">Suchbaum

</th>

<th style="width:21.4%">Suchen<br> (=Baumhöhe)

</th>

<th style="width:20%">Traversieren zum<br>Nachbarknoten

</th>

<th style="width:20%">Einfügen

</th>

<th style="width:21.4%">Löschen

</th></tr>

<tr>

</td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(\log n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/74a9dfea91c47d1c6563e89bbcd891771b91acfa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.413ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(\log n)}" loading="lazy"></span>

</td>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(1)\!<\!{\mathcal {O}}(\log n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/74c5a7ec5094d590d56c28e057e1478a3b243c0c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.559ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(1)\!<\!{\mathcal {O}}(\log n)}" loading="lazy"></span>

</td>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(1)\!<\!{\mathcal {O}}(\log n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/74c5a7ec5094d590d56c28e057e1478a3b243c0c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.559ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(1)\!<\!{\mathcal {O}}(\log n)}" loading="lazy"></span>

</td>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(1)\!<\!{\mathcal {O}}(\log n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/74c5a7ec5094d590d56c28e057e1478a3b243c0c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.559ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(1)\!<\!{\mathcal {O}}(\log n)}" loading="lazy"></span>

</td></tr>

<tr>

<td><a href="Rot-Schwarz-Baum" title="Rot-Schwarz-Baum">Rot-Schwarz-Baum</a>

</td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(\log n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/74a9dfea91c47d1c6563e89bbcd891771b91acfa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.413ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(\log n)}" loading="lazy"></span>

</td>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(1)\!<\!{\mathcal {O}}(\log n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/74c5a7ec5094d590d56c28e057e1478a3b243c0c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.559ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(1)\!<\!{\mathcal {O}}(\log n)}" loading="lazy"></span>

</td>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(1)\!<\!{\mathcal {O}}(\log n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/74c5a7ec5094d590d56c28e057e1478a3b243c0c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.559ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(1)\!<\!{\mathcal {O}}(\log n)}" loading="lazy"></span>

</td>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(1)\!<\!{\mathcal {O}}(\log n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/74c5a7ec5094d590d56c28e057e1478a3b243c0c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.559ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(1)\!<\!{\mathcal {O}}(\log n)}" loading="lazy"></span>

</td></tr>

<tr>

</td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(\log n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/74a9dfea91c47d1c6563e89bbcd891771b91acfa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.413ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(\log n)}" loading="lazy"></span>

</td>

<td>

</td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(\log n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/74a9dfea91c47d1c6563e89bbcd891771b91acfa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.413ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(\log n)}" loading="lazy"></span>

</td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(\log n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/74a9dfea91c47d1c6563e89bbcd891771b91acfa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.413ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(\log n)}" loading="lazy"></span>

</td></tr>

<tr>

</td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(\log n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/74a9dfea91c47d1c6563e89bbcd891771b91acfa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.413ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(\log n)}" loading="lazy"></span>

</td>

<td>

</td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(\log n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/74a9dfea91c47d1c6563e89bbcd891771b91acfa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.413ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(\log n)}" loading="lazy"></span>

</td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(\log n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/74a9dfea91c47d1c6563e89bbcd891771b91acfa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.413ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(\log n)}" loading="lazy"></span>

</td></tr>

<tr>

<td><a href="Splay-Baum" title="Splay-Baum">Splay-Baum</a>

</td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(\log n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/74a9dfea91c47d1c6563e89bbcd891771b91acfa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.413ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(\log n)}" loading="lazy"></span> <sup>1</sup> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \!<\!{\mathcal {O}}(n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \!<\!{\mathcal {O}}(n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2c98e278508d39516b2f6955fd3ccefc5f5ed77b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.387ex; width:7.12ex; height:2.843ex;" alt="{\displaystyle \!<\!{\mathcal {O}}(n)}" loading="lazy"></span>

</td>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(1)\!<\!{\mathcal {O}}(n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3eec8f01dda98db10a2b6164a5d2c14808bcaa00.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.2ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(1)\!<\!{\mathcal {O}}(n)}" loading="lazy"></span>

</td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(\log n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/74a9dfea91c47d1c6563e89bbcd891771b91acfa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.413ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(\log n)}" loading="lazy"></span> <sup>1</sup> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \!<\!{\mathcal {O}}(n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \!<\!{\mathcal {O}}(n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2c98e278508d39516b2f6955fd3ccefc5f5ed77b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.387ex; width:7.12ex; height:2.843ex;" alt="{\displaystyle \!<\!{\mathcal {O}}(n)}" loading="lazy"></span>

</td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(\log n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/74a9dfea91c47d1c6563e89bbcd891771b91acfa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.413ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(\log n)}" loading="lazy"></span> <sup>1</sup> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \!<\!{\mathcal {O}}(n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \!<\!{\mathcal {O}}(n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2c98e278508d39516b2f6955fd3ccefc5f5ed77b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.387ex; width:7.12ex; height:2.843ex;" alt="{\displaystyle \!<\!{\mathcal {O}}(n)}" loading="lazy"></span>

</td></tr>

<tr>

<td><a href="Bin%C3%A4rer_Suchbaum" title="Binärer Suchbaum">binärer Suchbaum</a>

</td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(\log n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/74a9dfea91c47d1c6563e89bbcd891771b91acfa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.413ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(\log n)}" loading="lazy"></span> <sup>2</sup> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \!<\!{\mathcal {O}}(n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \!<\!{\mathcal {O}}(n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2c98e278508d39516b2f6955fd3ccefc5f5ed77b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.387ex; width:7.12ex; height:2.843ex;" alt="{\displaystyle \!<\!{\mathcal {O}}(n)}" loading="lazy"></span>

</td>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(1)\!<\!{\mathcal {O}}(n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3eec8f01dda98db10a2b6164a5d2c14808bcaa00.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.2ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(1)\!<\!{\mathcal {O}}(n)}" loading="lazy"></span>

</td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(1)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5aeb15c854068604d35a2dd82a925899fafd3690.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.822ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(1)}" loading="lazy"></span>

</td>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(\log n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/74a9dfea91c47d1c6563e89bbcd891771b91acfa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.413ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(\log n)}" loading="lazy"></span> <sup>2</sup> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \!<\!{\mathcal {O}}(n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \!<\!{\mathcal {O}}(n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2c98e278508d39516b2f6955fd3ccefc5f5ed77b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.387ex; width:7.12ex; height:2.843ex;" alt="{\displaystyle \!<\!{\mathcal {O}}(n)}" loading="lazy"></span>

</td></tr>

<tr>

<td colspan="5" align="left"><sup>1</sup> Abhängig vom Zugriffsmuster der Anwendung können bei Splay-Bäumen auch unterlogarihmische mittlere <a href="Laufzeit_(Informatik)" title="Laufzeit (Informatik)">Laufzeiten</a> vorkommen.<br>

<p><sup>2</sup> Unter den unbalancierten <a href="Bin%C3%A4rer_Suchbaum" title="Binärer Suchbaum">binären Suchbäumen</a> gibt es <a href="Baum_(Graphentheorie)" title="Baum (Graphentheorie)">Bäume</a>, bei denen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(\log n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(\log n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/74a9dfea91c47d1c6563e89bbcd891771b91acfa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.413ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(\log n)}" loading="lazy"></span> nicht garantiert werden kann. Die Angabe <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}(\log n)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}(\log n)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/74a9dfea91c47d1c6563e89bbcd891771b91acfa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.413ex; height:2.843ex;" alt="{\displaystyle {\mathcal {O}}(\log n)}" loading="lazy"></span> gilt jedoch im Mittel über alle möglichen Baumformen hinweg.

</p>

</td></tr></tbody></table>

<p>Neben den vorgenannten <a href="Operation_(Informatik)" title="Operation (Informatik)">Operationen</a> kommen weitere in Betracht:

</p>

<ul><li>Zugriff auf spezielle Elemente, wie z. B. das kleinste Element</li>

<li>Verschmelzen von Suchbäumen</li></ul>

<p><a href="Laufzeit_(Informatik)" title="Laufzeit (Informatik)">Laufzeitmessungen</a> einiger <a href="Suchalgorithmen" class="mw-redirect" title="Suchalgorithmen">Suchalgorithmen</a> anhand realistischer Beispiele sind zu finden bei <a href="#Weblinks">Ben Pfaff</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Siehe_auch">Siehe auch</h2></div>

<ul><li><a href="Effizienz_(Informatik)" title="Effizienz (Informatik)">Effizienz (Informatik)</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>Alexander Reinefeld: <i>Spielbaum-Suchverfahren.</i> (= <i>Subreihe Künstliche Intelligenz.</i> Band 200). Springer, 1989, ISBN 3-540-50742-6.</li>

<li>A. Banzhaf, U. Boes, M. Kramer: <i>Steuerung von Erkennungsprozessen durch Baumsuchverfahren.</i> In: H. Burkhardt, K. H. Höhne, B. Neumann (Hrsg.): <i>Mustererkennung.</i> (= <i>Informatik-Fachberichte.</i> Band 219). Springer, Berlin / Heidelberg 1989, ISBN 3-540-51748-0.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

</p>

<ul><li>Ben Pfaff: <a rel="nofollow" class="external text" href="https://web.stanford.edu/~blp/papers/libavl.pdf"><i>Performance Analysis of BSTs in System Software.</i></a> (PDF; 309 kB). <a href="Stanford_University" title="Stanford University">Stanford University</a>, 2004. (englisch)</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text">Toal, Ray. <a rel="nofollow" class="external text" href="https://cs.lmu.edu/~ray/notes/abtrees/">"(a,b) Trees"</a></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><a href="#cite_ref-2">↑</a></span> <span class="reference-text">Der in den Knoten gespeicherte <i>Wert</i> fungiert als Teilstück des Suchschlüssels.</span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><a href="#cite_ref-3">↑</a></span> <span class="reference-text">GeeksforGeeks: <a rel="nofollow" class="external text" href="https://www.geeksforgeeks.org/ternary-search-tree/">Ternary Search Tree</a></span>

</li>

</ol>

<div>

Normdaten (Sachbegriff): <a href="Gemeinsame_Normdatei" title="Gemeinsame Normdatei">GND</a>: <span class="-print"><a rel="nofollow" class="external text" href="https://d-nb.info/gnd/4317574-0">4317574-0</a></span> </div>

</div></div></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-08-11" href="https://de.wikipedia.org/wiki/?title=Suchbaum&oldid=258770568">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>